package mht.practice.heap;

import mht.practice.sort.SortTestHelper;

/**
 * 原地堆排序  不用额外开空间
 * Created by MHT on 2017/8/26.
 */
public class HeapSort3 {

    private HeapSort3(){}

    // 交换堆中索引为i和j的两个元素
    private static void swap(Object[] arr, int i, int j){
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public static void sort(Comparable[] arr){

        int n = arr.length;
        for (int i = (n-1-1)/2;i>=0;i--){
            shiftDown(arr,n,i);
        }

        for (int i = n-1;i>0;i--){
            swap(arr,0,i);
            shiftDown(arr,i,0);
        }


    }

    // 原始的shiftDown过程
    private static void shiftDown(Comparable[] arr, int n, int k){

        while( 2*k+1 < n ){
            int j = 2*k+1;
            if( j+1 < n && arr[j+1].compareTo(arr[j]) > 0 )
                j += 1;

            if( arr[k].compareTo(arr[j]) >= 0 )break;

            swap( arr, k, j);
            k = j;
        }
    }

    // 优化的shiftDown过程， 使用赋值的方式取代不断的swap
    private static void shiftDownBetter(Comparable[] arr, int n, int k){

        Comparable e = arr[k];
        while( 2*k+1 < n ){
            int j = 2*k+1;
            if( j+1 < n && arr[j+1].compareTo(arr[j]) > 0 )
                j += 1;

            if( e.compareTo(arr[j]) >= 0 )break;

            arr[k] = arr[j];
            k = j;
        }
        arr[k] = e;
    }


    // 测试 HeapSort
    public static void main(String[] args) {

        int N = 1000000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        SortTestHelper.testSort("mht.practice.heap.HeapSort3", arr);
    }
}
